МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра САПР Звіт до лабораторної роботи №3 на тему: «ІНДЕКСНО-ПОСЛІДОВНИЙ МЕТОД ДОСТУПУ ДО ФАЙЛІВ НА ЗОВНІШНІХ ЗАПАМ’ЯТОВУЮЧИХ ПРИСТРОЯХ»  Мета: Розглянути органiзацiю i ведення файлiв iндексно-послiдовного доступу; набути практичнi навички у програмуваннi алгоритмiв iндексно-послiдовного доступу до файлiв на зовнiшнiх запам'ятовуючих пристроях. Завдання: Написати програму, яка реалiзує алгоритми роботи iндексно-послiдов ного методу доступу до iнформацiї на зовнiшнiх носiях: Створення БД. Вставка елементу в БД. Видалення запису з БД. Модифікація запису. Пошук. Перегляд. Теоретичні відомості: Якщо файл впорядкований по ключах, то звичайно для адресацiї використовується таблиця, що називається iндексом. При звертаннi до таблицi задається ключ шуканого запису, а результатом процедури пошуку у таблицi є вiдносна адреса запису у зовнiшнiй пам'ятi. Якщо для адресацiї файла використовується iндекс, ЕОМ в основному здiйснює пошук в iндексi, а не у файлi даних. При цьому суттєво економиться час, але потребується пам'ять для зберiгання iндексу. Існує багато iндексних методiв доступу, в основi яких лежить принцип створення окремого iндексного файла. індексний файл значно менший вiд власне бази даних, i, оскiльки вiн може повнiстю зберiгатися в оперативнiй пам'ятi, швидкодiя пошуку у ньому значно вища. В iндексно-послiдовному методi доступу iндексний файл завжди впорядкований за так званим первинним ключем (головний атрибут фiзичного запису). Оскiльки у цьому методi i записи файла даних впорядкованi за ключем, iндекс звичайно мiстить не посилання на окремий запис, а посилання на блоки записiв, всерединi яких можна здiйснювати пошук i сканування. Збереження посилань на блоки записiв, а не на окремi записи значно зменшує розмiр iндексу. Наприклад, якщо в блоцi зберiгається 10 записiв, то для нього в iндексному файлi буде одна стаття, а не 10, i розмiр iндексного файла зменшується в 10 разiв. Індексний файл i файл даних органiзованi послiдовно. Індексний файл мiстить лише максимальнi значення первинних ключiв записiв кожного блока. Послiдовна органiзацiя індексного файла допускає iндексацiю його вмiсту. Записи iндексу групуються у блоки, якi можна iндексувати. Індексний файл наступного рiвня мiстить вказiвники на індекснi файли попереднього рiвня. При роботi з великими файлами така органiзацiя дає змогу покращити характеристики доступу. Індексний файл складається з пар (значення ключа, адреса блока). Пара (v,b) з'являється у файлi iндексу, якщо перший запис у блоцi з адресою b має значення ключа v. Перше поле є ключем файла iндексу, який пiдтримується вiдсортованим за значенням свого ключа. В iндексно-послiдовному файлi необхiдно отримати вiдповiдi на запитання: якщо задане значення ключа v1 для iндексного файла, знайти в iндексi такий запис (v2,b), що v2<=v1 i або (v2,b) ї останнiм записом у iндексi, або наступний запис (v3,b) задовольняє умову v1<v3. У цiй ситуацiї говорять, що v2 покриває v1. Отже, ми знаходимо блок b головного файла, що мiстить запис iз значенням ключа v1, оскiльки файл iндексу з гарантiїю є вiдсортованим. Пiд час вставляння нових записiв виникає необхiднiсть або пересортовувати файл, або вносити новi записи в окрему дiлянку i органiзувати вказiвники на цi записи. Цi записи помiщаються у дiлянку переповнення. Такi файли перiодично реорганiзовуються, т.б. записи файла заново сортуються i здiйснюються вiдповiднi змiни в iндексi. Для уникнення частого використання процедури реорганiзацiї у файлi передбачаються позицiї з порожнiми записами (подiл файла даних на блоки). Але даний метод не дає змоги повнiстю уникнути виконання процедури реорганiзацiї. Розглянемо операцiї пошуку, вставляння, видалення i модифiкацiї над вiдсортованим файлом iз записами, не закрiпленими вказiвниками за фіксованими адресами. Цi 4-и операцiї потребують вставляння, видалення, модифiкацiї у файлi iндексу. Вхiдний вiдсортований файл мiститься у по...